/*
	Ajanta - Java Linear Programming Library

	Copyright 2010 Raghu Kaippully.

	Licensed under the Apache License, Version 2.0 (the "License");
	you may not use this file except in compliance with the License.
	You may obtain a copy of the License at

    	http://www.apache.org/licenses/LICENSE-2.0

	Unless required by applicable law or agreed to in writing, software
	distributed under the License is distributed on an "AS IS" BASIS,
	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	See the License for the specific language governing permissions and
	limitations under the License.
 */

package logic.simplex.solver.internal.simplex;

import java.util.List;

import logic.simplex.model.LPConstraint;
import logic.simplex.model.LPProblem;
import logic.simplex.model.LPVariable;
import logic.simplex.model.Term;

/**
 * Tableau used by simplex solver
 */
public class Tableau {

	private static final String ObjectiveFunctionVariableName = "OBJECTIVE-FUNCTION";

	/**
	 * Number of rows in the tableau
	 */
	private int rowCount;

	/**
	 * Number of columns in the tableau
	 */
	private int columnCount;

	/**
	 * The array holding tableau values
	 */
	private double[][] tableauArray;

	/**
	 * The list of basic variables corresponding to each row of the tableau
	 */
	private TableauLabel basicVariables;

	/**
	 * Variable representing the objecting function
	 */
	LPVariable objectiveFunctionVariable = new LPVariable(ObjectiveFunctionVariableName);

	/**
	 * The column headers of this tableau.
	 */
	private TableauLabel header;

	/**
	 * Constructs an initial tableau with the constraints and objective function of the
	 * given LP problem
	 * 
	 * @param problem
	 *            problem to initialize this tableau with
	 */
	public Tableau(LPProblem problem) {
		/* one slack variable per constraint */
		int slackVariableCount = problem.getConstraints().size();
		/*
		 * Find how many rows we need - one for each slack variable and an additional one
		 * for the objective function variable
		 */
		rowCount = slackVariableCount + 1;
		/*
		 * Find how many columns we need - one for each problem variable, one for each
		 * slack variable, one for the objective function variable and one answer column
		 */
		int problemVariableCount = problem.getAllVariables().size();
		columnCount = problemVariableCount + slackVariableCount + 2;
		header = new TableauLabel(columnCount - 1);

		initializeTableauArray(problem);

		/* Setup basic variables */
		basicVariables = new TableauLabel(rowCount);
		for (int i = 0; i < slackVariableCount; i++) {
			LPVariable var = new LPVariable("SLACK-" + i);
			basicVariables.setVariable(var, i);
			header.setVariable(var, problemVariableCount + i);
		}
		basicVariables.setVariable(objectiveFunctionVariable, rowCount - 1);
		header.setVariable(objectiveFunctionVariable, problemVariableCount
			+ slackVariableCount);
	}

	/* Populate values into the tableau array */
	private void initializeTableauArray(LPProblem problem) {
		tableauArray = new double[rowCount][columnCount];
		int problemVariableCount = problem.getAllVariables().size();

		List<LPConstraint> constraints = problem.getConstraints();
		for (int rowIndex = 0; rowIndex < constraints.size(); rowIndex++) {
			LPConstraint constraint = constraints.get(rowIndex);
			for (Term term : constraint.getLHSExpression().getTerms()) {
				int columnIndex = getColumnIndex(term);
				tableauArray[rowIndex][columnIndex] = term.coefficient;
			}

			/* slack variable coefficient */
			switch (constraint.getOperator()) {
			case LessOrEqual:
				tableauArray[rowIndex][problemVariableCount + rowIndex] = 1;
				break;
			case GreaterOrEqual:
				tableauArray[rowIndex][problemVariableCount + rowIndex] = -1;
				break;
			}

			/* answer column */
			tableauArray[rowIndex][columnCount - 1] = constraint.getRHSConstant();
		}

		/* Row for objective function */
		for (Term term : problem.getObjectiveFunction().getTerms()) {
			int columnIndex = getColumnIndex(term);
			tableauArray[rowCount - 1][columnIndex] = -term.coefficient;
		}

		/* objective function variable coefficient */
		tableauArray[rowCount - 1][columnCount - 2] = 1;

		/* answer column */
		tableauArray[rowCount - 1][columnCount - 1] = 0;
	}

	/* To which column will this term go? */
	private int getColumnIndex(Term term) {
		return header.getOrAddIndex(term.variable);
	}

	/**
	 * The pivot column of the tableau is the most negative value in the bottom row. This
	 * method returns the column index of the pivot column. If no pivot column is found
	 * this method returns -1.
	 * 
	 * @return pivot column index of this tableau, or -1 if no pivot column was found
	 */
	public int getPivotColumnIndex() {
		double minValue = 0;
		int minIndex = -1;
		for (int i = 0; i < columnCount - 1; i++) {
			if (tableauArray[rowCount - 1][i] < minValue) {
				minValue = tableauArray[rowCount - 1][i];
				minIndex = i;
			}
		}
		return minIndex;
	}

	/**
	 * The pivot row of the tableau is the row with the smallest ratio a/b where a is the
	 * value in the answer column of the tableau and b is a positive value in the pivot
	 * column of that row. If no pivot row is found this method returns -1.
	 * 
	 * @return pivot row index of this tableau, or -1 if no pivot row was found
	 */
	public int getPivotRowIndex(int pivotColumnIndex) {
		double minRatio = Double.MAX_VALUE;
		int minIndex = -1;
		for (int i = 0; i < rowCount - 1; i++) {
			double testVal = tableauArray[i][pivotColumnIndex];
			if (testVal > 0) {
				double answerVal = tableauArray[i][columnCount - 1];
				double testRatio = answerVal / testVal;
				if (testRatio < minRatio) {
					minRatio = testRatio;
					minIndex = i;
				}
			}
		}
		return minIndex;
	}

	/**
	 * "Clears" the pivot using row operations
	 * 
	 * @param pivotRow
	 * @param pivotColumn
	 */
	public void clearPivotColumn(int pivotRow, int pivotColumn) {
		/*
		 * The row operation to clear the pivot column in row i is mRi - nRp where m is
		 * the tableau value at (pivotRow, pivotColumn) and n is the value at (i,
		 * pivotColumn)
		 */
		double m = tableauArray[pivotRow][pivotColumn];
		for (int i = 0; i < rowCount; i++) {
			if (i != pivotRow && tableauArray[i][pivotColumn] != 0) {
				double n = tableauArray[i][pivotColumn];
				for (int j = 0; j < columnCount; j++) {
					tableauArray[i][j] = (m * tableauArray[i][j])
						- (n * tableauArray[pivotRow][j]);
				}
			}
		}

		/* Change the basic variable */
		basicVariables.setVariable(header.getVariable(pivotColumn), pivotRow);
	}

	/**
	 * Returns the value of the given variable corresponding to the optimal solution.
	 */
	double getSolutionValue(LPVariable variable) {
		int index = basicVariables.getIndex(variable);
		return index == -1 ? 0 : tableauArray[index][columnCount - 1]
			/ tableauArray[index][header.getIndex(variable)];
	}
}
